package Acm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class ASmiloandMonsters {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken();
        int m = (int) st.nval;
        for (int p = 0; p < m; p++) {
            st.nextToken();
            int n = (int) st.nval;
            Long[] arr = new Long[n];
            for (int i = 0; i < n; i++) {
                st.nextToken();
                arr[i] = (long) st.nval;
            }
            Arrays.sort(arr);
            int left = 0;
            int right = n - 1;
            long sum = 0;
            long output = 0;
            while (true) {
                if (left > right) {
                    break;
                }
                if (left == right) {
                    if (sum == arr[right]){
                        output++;
                        break;
                    }
                    if(arr[left] == 1){
                        output++;
                        break;
                    }
                    if((arr[left] + sum)%2 == 0){
                        long tmp = (sum+arr[left])/2;
                        output += tmp - sum;
                        output ++;
                        break;
                    }else{
                        output += ((sum+arr[left])/2)-sum;
                        output +=2;
                        break;
                    }
                }
                if (sum == arr[right]) {
                    sum = 0;
                    output++;
                    right--;
                } else if (sum + arr[left] > arr[right]) {
                    output++;
                    output +=  arr[right] - sum;
                    long tmp =sum + arr[left] - arr[right];
                    sum = 0;
                    right--;
                    arr[left] = tmp;
                    if(left == right){
                        continue;
                    }
                    sum = tmp;
                    left++;
                    output += sum;

                } else {
                    sum += arr[left];
                    output += arr[left];
                    left++;
                }
            }
            System.out.println(output);
        }

    }
}
